package com.antsing.structure.queue;

/**
 * 循环队列
 *  #fifo：先进先出
 *  #节省空间
 *  #参考https://leetcode-cn.com/explore/learn/card/queue-stack/216/queue-first-in-first-out-data-structure/864/
 */
public class CircularQueue {
    /**
     * 容量
     */
    private int capacity;
    private int data[];
    private int head = 0;
    private int tail = 0;
    /**
     * 队列当前元素个数
     */
    private int size=0;

    public CircularQueue(int capacity){
        this.capacity = capacity;
        data = new int[capacity];
    }

    /**
     * 入列
     * @param value
     * @return
     */
    public boolean enqueue(int value){
        if(value <=0){
            return false;
        }
        if(size < capacity){
            data[tail] = value;
            size++;
            if(tail==capacity-1){
                tail=0;
            }else{
                tail++;
            }
            return true;
        }else{
            return false;
        }
    }

    /**
     * 出列
     * @return
     */
    public int dequeue(){
        if(size == 0){
            return -1;
        }
        int result = data[head];
        data[head] = 0;
        if(head == capacity-1){
            head=0;
        }else{
            head++;
        }
        size--;
        return result;
    }
    public void print(){
        for(int i=0;i<capacity;i++){
            System.out.println(data[i]);
        }
    }

    public static void main(String[] args) {
        int capacity = 10;
        CircularQueue circularQueue = new CircularQueue(capacity);
        circularQueue.print();
        for(int i = 0;i<12;i++){
            circularQueue.enqueue(i+1);
        }
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        circularQueue.enqueue(99);
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        circularQueue.enqueue(88);
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
        System.out.println("出列:"+circularQueue.dequeue());
        circularQueue.print();
    }
}
